#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAXSIZE 10
int list[MAXSIZE];

void InitList(){
    srand(time(0));
    for(int i = 0; i < MAXSIZE; i++){
        list[i] = rand() % 200;
        for (int j = 0; j < i; j++)
        {
            if (list[i] == list[j])
            {
                i = 0;
            }
        }
    }
}

int PrintList(int *a){
    for (int i = 0; i < MAXSIZE; i++)
    {
        printf("%d ", a[i]);
    }
}

int difference(int a, int b){
	return (a > b) ? (a - b) : (b - a);
}

void FCFS(int start){
    int order[MAXSIZE];
    int sum = 0;
    printf("\nYou are using FCFS algorithm.\n");
    printf("\nHere is the service order:\n");
    for (int i = 0; i < MAXSIZE; i++)
    {
        printf("%d\n", list[i]);
    }
    order[0] = start;
    for (int j = 1; j < MAXSIZE; j++)
    {
        order[j] = list[j-1];
    }
    printf("\nThe total distance is:");
    for (int k = 0; k < MAXSIZE; k++)
    {
        printf("%d", difference(order[k], list[k]));
        if (k != 9)
        {
            printf("+");
        }
        sum += difference(order[k], list[k]);
    }
    printf("=%d\n", sum);
    float average = (float)sum/(float)MAXSIZE;
    printf("\nThe average dictance is: %f\n\n\n", average);
}

void SSTF(int start){
	int temp[MAXSIZE];
    int ord[MAXSIZE];
    int staff;
    int dif = 200;
    int now = start;
    int sum = 0;
	for (int i = 0; i < MAXSIZE; i++)
    {
        temp[i] = list[i];
    }
    for (int i = 0; i < MAXSIZE; i++)
    {
        for (int j = 0; j < MAXSIZE; j++)
        {
            if (dif > difference(now, temp[j]))
            {
                dif = difference(now, temp[j]);
                staff = j;
            }
        }
        now = temp[staff];
        ord[i] = staff;
        temp[staff] = 2000;
        dif = 200;
    }
    printf("\nYou are using SSTF algorithm.\n");
    printf("\nHere is the service order:\n");
    printf("%d\n", list[ord[0]]);
    temp[0] = start;
    for (int i = 1; i < MAXSIZE; i++)
    {
        printf("%d\n", list[ord[i]]);
        temp[i] = list[ord[i-1]];
    }
    printf("\nThe total distance is:");
    for (int k = 0; k < MAXSIZE; k++)
    {
        printf("%d", difference(temp[k], list[ord[k]]));
        if (k != 9)
        {
            printf("+");
        }
        sum += difference(temp[k], list[ord[k]]);
    }
    printf("=%d\n", sum);
    float average = (float)sum/(float)MAXSIZE;
    printf("\nThe average dictance is: %f\n\n\n", average);
}

void SCAN(int start){
    int temp[MAXSIZE];
    int now = start;
    int staff;
    int dif;
    int ord[MAXSIZE];
    int t;
    int sum = 0;
    for (int i = 0; i < MAXSIZE; i++)
    {
        temp[i] = list[i];
    }
    //����ɨ��
    for (int i = 0; i < MAXSIZE; i++)
    {
        staff = 10;
        dif = 200;
        for (int j = 0; j < MAXSIZE; j++)
        {
            if (dif > temp[j] - now && temp[j] > now){
                dif = temp[j] - now;
                staff = j;
            }
        }
        if (staff != 10)
        {
            now = temp[staff];
            temp[staff] = 2000;
            ord[i] = staff;
        }
        else{
            staff = i;
            break;
        }
    }
    t = staff;
    for (int i = t; i < MAXSIZE; i++)
    {
        staff = 10;
        dif = 200;
        for (int j = 0; j < MAXSIZE; j++)
        {
            if (dif > now - temp[j] && now > temp[j])
            {
                dif = now - temp[j];
                staff = j;
            }
        }
        if (staff != 10)
        {
            now = temp[staff];
            temp[staff] = 2000;
            ord[i] = staff;
        }
        else{
            break;
        }
    }
    printf("\nYou are using SCAN algorithm.\n");
    printf("\nHere is the service order:\n");
    printf("%d\n", list[ord[0]]);
    temp[0] = start;
    for (int i = 1; i < MAXSIZE; i++)
    {
        printf("%d\n", list[ord[i]]);
        temp[i] = list[ord[i-1]];
    }
    printf("\nThe total distance is:");
    for (int k = 0; k < MAXSIZE; k++)
    {
        printf("%d", difference(temp[k], list[ord[k]]));
        if (k != 9)
        {
            printf("+");
        }
        sum += difference(temp[k], list[ord[k]]);
    }
    printf("=%d\n", sum);
    float average = (float)sum/(float)MAXSIZE;
    printf("\nThe average dictance is: %f\n\n\n", average);
}

void CSCAN(int start){
    int temp[MAXSIZE];
    int now = start;
    int staff;
    int dif;
    int ord[MAXSIZE];
    int t;
    int sum = 0;
    for (int i = 0; i < MAXSIZE; i++)
    {
        temp[i] = list[i];
    }
    //����ɨ��
    for (int i = 0; i < MAXSIZE; i++)
    {
        staff = 10;
        dif = 200;
        for (int j = 0; j < MAXSIZE; j++)
        {
            if (dif > temp[j] - now && temp[j] > now){
                dif = temp[j] - now;
                staff = j;
            }
        }
        if (staff != 10)
        {
            now = temp[staff];
            temp[staff] = 2000;
            ord[i] = staff;
        }
        else{
            staff = i;
            break;
        }
    }
    t = staff;
    now = 0;
    for (int i = t; i < MAXSIZE; i++)
    {
        staff = 10;
        dif = 200;
        for (int j = 0; j < MAXSIZE; j++)
        {
            if (dif > temp[j] - now && temp[j] > now){
                dif = temp[j] - now;
                staff = j;
            }
        }
        if (staff != 10)
        {
            now = temp[staff];
            temp[staff] = 2000;
            ord[i] = staff;
        }
        else{
            staff = i;
            break;
        }
    }
    printf("\nYou are using CSCAN algorithm.\n");
    printf("\nHere is the service order:\n");
    printf("%d\n", list[ord[0]]);
    temp[0] = start;
    for (int i = 1; i < MAXSIZE; i++)
    {
        printf("%d\n", list[ord[i]]);
        temp[i] = list[ord[i-1]];
    }
    printf("\nThe total distance is:");
    for (int k = 0; k < MAXSIZE; k++)
    {
        printf("%d", difference(temp[k], list[ord[k]]));
        if (k != 9)
        {
            printf("+");
        }
        sum += difference(temp[k], list[ord[k]]);
    }
    printf("=%d\n", sum);
    float average = (float)sum/(float)MAXSIZE;
    printf("\nThe average dictance is: %f\n\n\n", average);
}

int main(){
    int start;
    int key;
    printf("Thanks for using Disk Scheduling Algorithm\n\n");
    printf("You've been given a set of Track Number:\n");
	InitList();
    PrintList(list);
    do{
        printf("\n\nYou'll start with number(0~199):\n");
        scanf("%d", &start);
    } while(!(0<=start && start<=199));
    do{
        do{
            printf("\nYou will use:\n");
            printf("FCFS[0]      SSTF[1]\nSCAN[2]      CSCAN[3]\nQUIT[4]\n\n");
            scanf("%d", &key);
        } while(!(0 <= key <= 3));
        switch (key)
        {
        case 0:
            FCFS(start);
            break;
        
        case 1:
        	SSTF(start);
        	break;
        
        case 2:
        	SCAN(start);
        	break;
        	
        case 3:
        	CSCAN(start);
        	break;
			 
        default:
            break;
        }
    } while(key != 4);
}
